/* 

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/subsets-ii/solution/zi-ji-ii-by-leetcode-solution-7inq/

// 方法一：迭代法实现子集枚举
var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    const res = [];
    const n = nums.length;
    for (let mask = 0; mask < (1 << n); ++mask) {
        const temp = [];
        let flag = true;
        for (let i = 0; i < n; ++i) {
            if ((mask & (1 << i)) !== 0) {
                if (i > 0 && (mask >> (i - 1) & 1) === 0 && nums[i] === nums[i - 1]) { // 右移后mask值不会变，而是产生一个新的数值
                    flag = false;
                    break;
                }
                temp.push(nums[i]);
            }
        }
        if (flag) {
            res.push(temp);
        }
    }
    return res;
};

// 方法二：递归法实现子集枚举
var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    const res = [],
        temp = [];
    const len = nums.length;

    const dfs = (choosePre, cur, nums) => {
        if (cur === len) {
            res.push(temp.slice());
            return;
        }
        dfs(false, cur + 1, nums);
        // 这个判断的位置要理解
        if (!choosePre && cur > 0 && nums[cur - 1] === nums[cur]) {
            return;
        }
        temp.push(nums[cur]);
        dfs(true, cur + 1, nums);
        temp.pop();
    }

    dfs(false, 0, nums);

    return res;
};